
//
//  Deque.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/14.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// Double-ended queue
public final class Deque<Element> {
    
    // a Deque does not wrap a Vector but a LinkedList
    // because of efficency consideration
    let _storage: LinkedList<Element>
    
    /// whether the Deque is empty
    public var isEmpty: Bool { return _storage.isEmpty }
    /// Indicates number of elements in Deque
    public var count: Int { return _storage.count }
    
    /// Initialize a empty Deque
    public init() {
        _storage = LinkedList()
    }
    
    /// Initialize a Deque through another Deque
    public init(_ other: Deque<Element>) {
        _storage = LinkedList(other._storage)
    }

    /// peek element at front
    public func peekFront() -> Element? {
        if _storage.isEmpty { return nil }
        return _storage.first?.value
    }
    
    /// peek element at back
    public func peekBack() -> Element? {
        if _storage.isEmpty { return nil }
        return _storage.last?.value
    }
    
    /// enqueue nomally
    public func enqueue(_ element: Element) {
        _storage.insertAsLast(element)
    }
    
    /// enqueue at front
    public func enqueueFront(_ element: Element) {
        _storage.insertAsFirst(element)
    }

    /// dequeue normally
    public func dequeue() -> Element? {
        guard let firstNode = _storage.first else { return nil }
        return _storage.remove(firstNode)
    }
    
    /// dequeue at back
    public func dequeueBack() -> Element? {
        guard let lastNode = _storage.last else { return nil }
        return _storage.remove(lastNode)
    }
}

extension Deque: ExpressibleByArrayLiteral {
    public convenience init(arrayLiteral elements: Element...) {
        self.init()
        elements.forEach { _storage.insertAsLast($0) }
    }
}
